#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
    void recursion(TreeNode * node, int & count)
    {
        if(node == nullptr)
        {
            return;
        }
        count++;
        recursion(node->left, count);
        recursion(node->right, count);
    }
public:
    int countNodes(TreeNode* root) 
    {
        int count = 0;
        recursion(root, count);
        return count;
    }
};

// 辅助函数：创建二叉树节点
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

// 辅助函数：释放二叉树内存
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    Solution solution;
    
    cout << "=== LeetCode 222. 完全二叉树的节点个数 测试案例 ===" << endl;
    
    // 测试案例1: 示例1 - [1,2,3,4,5,6] (完全二叉树)
    cout << "\n测试案例1: [1,2,3,4,5,6] (完全二叉树)" << endl;
    TreeNode* root1 = createNode(1);
    root1->left = createNode(2);
    root1->right = createNode(3);
    root1->left->left = createNode(4);
    root1->left->right = createNode(5);
    root1->right->left = createNode(6);
    
    int result1 = solution.countNodes(root1);
    cout << "输入: [1,2,3,4,5,6]" << endl;
    cout << "输出: " << result1 << endl;
    cout << "期望: 6" << endl;
    
    // 测试案例2: 示例2 - [] (空树)
    cout << "\n测试案例2: [] (空树)" << endl;
    TreeNode* root2 = nullptr;
    
    int result2 = solution.countNodes(root2);
    cout << "输入: []" << endl;
    cout << "输出: " << result2 << endl;
    cout << "期望: 0" << endl;
    
    // 测试案例3: 只有一个节点 [1]
    cout << "\n测试案例3: 只有一个节点 [1]" << endl;
    TreeNode* root3 = createNode(1);
    
    int result3 = solution.countNodes(root3);
    cout << "输入: [1]" << endl;
    cout << "输出: " << result3 << endl;
    cout << "期望: 1" << endl;
    
    // 测试案例4: 完全二叉树 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
    cout << "\n测试案例4: 满二叉树 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]" << endl;
    TreeNode* root4 = createNode(1);
    root4->left = createNode(2);
    root4->right = createNode(3);
    root4->left->left = createNode(4);
    root4->left->right = createNode(5);
    root4->right->left = createNode(6);
    root4->right->right = createNode(7);
    root4->left->left->left = createNode(8);
    root4->left->left->right = createNode(9);
    root4->left->right->left = createNode(10);
    root4->left->right->right = createNode(11);
    root4->right->left->left = createNode(12);
    root4->right->left->right = createNode(13);
    root4->right->right->left = createNode(14);
    root4->right->right->right = createNode(15);
    
    int result4 = solution.countNodes(root4);
    cout << "输入: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]" << endl;
    cout << "输出: " << result4 << endl;
    cout << "期望: 15" << endl;
    
    // 测试案例5: 不完整的完全二叉树 [1,2,3,4,5,6,7,8]
    cout << "\n测试案例5: 不完整的完全二叉树 [1,2,3,4,5,6,7,8]" << endl;
    TreeNode* root5 = createNode(1);
    root5->left = createNode(2);
    root5->right = createNode(3);
    root5->left->left = createNode(4);
    root5->left->right = createNode(5);
    root5->right->left = createNode(6);
    root5->right->right = createNode(7);
    root5->left->left->left = createNode(8);
    
    int result5 = solution.countNodes(root5);
    cout << "输入: [1,2,3,4,5,6,7,8]" << endl;
    cout << "输出: " << result5 << endl;
    cout << "期望: 8" << endl;
    
    // 测试案例6: 只有左子树的完全二叉树 [1,2,4]
    cout << "\n测试案例6: 只有左子树的完全二叉树 [1,2,4]" << endl;
    TreeNode* root6 = createNode(1);
    root6->left = createNode(2);
    root6->left->left = createNode(4);
    
    int result6 = solution.countNodes(root6);
    cout << "输入: [1,2,4]" << endl;
    cout << "输出: " << result6 << endl;
    cout << "期望: 3" << endl;
    
    // 测试案例7: 两层完全二叉树 [1,2,3]
    cout << "\n测试案例7: 两层完全二叉树 [1,2,3]" << endl;
    TreeNode* root7 = createNode(1);
    root7->left = createNode(2);
    root7->right = createNode(3);
    
    int result7 = solution.countNodes(root7);
    cout << "输入: [1,2,3]" << endl;
    cout << "输出: " << result7 << endl;
    cout << "期望: 3" << endl;
    
    // 释放内存
    deleteTree(root1);
    // root2 已经是 nullptr，不需要释放
    deleteTree(root3);
    deleteTree(root4);
    deleteTree(root5);
    deleteTree(root6);
    deleteTree(root7);
    
    cout << "\n=== 测试完成 ===" << endl;
    
    return 0;
}